Back to course home
0% completed
Vote For New Content
Google Hard
Shortest Subarray with Sum at Least K (hard)
Solution: Shortest Subarray with Sum at Least K
Reverse Pairs (hard)
Solution: Reverse Pairs
Nth Magical Number (hard)
Solution: Nth Magical Number
Candy (hard)
Solution: Candy
Arithmetic Slices II - Subsequence (hard)
Solution: Arithmetic Slices II - Subsequence
Burst Balloons (hard)
Solution: Burst Balloons
Sum of Distances in Tree (hard)
Solution: Sum of Distances in Tree
Maximum Score of a Good Subarray (hard)
Solution: Maximum Score of a Good Subarray
Trapping Rain Water (hard)
Solution: Trapping Rain Water
First Missing Positive (hard)
Solution: First Missing Positive
Implement Trie (Prefix Tree) (medium)
Problem Statement
Design and implement a Trie (also known as a Prefix Tree). A trie is a tree-like data structure that stores a dynamic set of strings, and is particularly useful for searching for words with a given prefix.
Implement the Solution class:
Solution()Initializes the object.void insert(word)Insertswordinto the trie, making it available for future searches.bool search(word)Checks if the word exists in the trie.bool startsWith(word)Checks if any word in the trie starts with the given prefix.
Examples
-
Example 1:
- Input:
- Trie operations:
["Trie", "insert", "search", "startsWith"] - Arguments:
[[], ["apple"], ["apple"], ["app"]]
- Trie operations:
- Expected Output:
[-1, -1, 1, 1] - Justification: After inserting "apple", "apple" exists in the Trie. There is also a word that starts with "app", which is "apple".
- Input:
-
Example 2:
- Input:
- Trie operations:
["Trie", "insert", "search", "startsWith", "search"] - Arguments:
[[], ["banana"], ["apple"], ["ban"], ["banana"]]
- Trie operations:
- Expected Output:
[-1, -1, 0, 1, 1] - Justification: After inserting "banana", "apple" does not exist in the Trie but a word that starts with "ban", which is "banana", does exist.
- Input:
-
Example 3:
- Input:
- Trie operations:
["Trie", "insert", "search", "startsWith", "startsWith"] - Arguments:
[[], ["grape"], ["grape"], ["grap"], ["gr"]]
- Trie operations:
- Expected Output:
[-1, -1, 1, 1, 1] - Justification: After inserting "grape", "grape" exists in the Trie. There are words that start with "grap" and "gr", which is "grape".
- Input:
Constraints:
1 <= word.length, prefix.length <= 2000wordand prefixconsist only of lowercase English letters.- At most 3 * 104 calls in total will be made to insert, search, and startsWith.
Try it yourself
Try solving this question here:
Java
Saved to Cloud
. . . .
Solution: Combination Sum
Solution: Implement Trie (Prefix Tree)
Mark as Completed
On this page
Problem Statement
Examples
Try it yourself